111C - Petya and Spiders - CodeForces Solution

#include<iostream>
#include<cassert>
using namespace std;

int board[64][64];
int N, M;
int dx[5] = {0, 1, -1, 0, 0};
int dy[5] = {0, 0, 0, 1, -1};
int dp[64][1<<8][1<<8];
bool vis[64][1<<8][1<<8];

pair<int,int> nxtcell(int x, int y){
    int nx = x, ny = y + 1;
    if(ny >= M){
        ny = 0;
        nx = x+1;
    }
    if(nx >= N) return make_pair(-1, -1);
    else return make_pair(nx, ny);
}

int solve(int x, int y){
    if(x == -1) return 0;
    int pstate = 0, cstate = 0;
    if(y == 0 && x > 0){
        for (int i = 0; i < M; i++) if (board[x - 1][i] != 0) pstate |= (1 << i);
        for (int i = 0; i < M; i++) if (board[x][i] > 1) cstate |= (1 << i);
        if(vis[x][pstate][cstate]) return dp[x][pstate][cstate];
    }

    auto nxt = nxtcell(x, y);
    if(board[x][y] > 1) return solve(nxt.first, nxt.second);
    int ans = 0;
    for(int k=0;k<5;k++){
        int nx = x + dx[k], ny = y + dy[k];
        if(nx < 0 || nx >= N || ny < 0 || ny >= M || board[nx][ny] == 0) continue;
        int offset = 0;
        if(board[nx][ny] == 0) offset -= 1;
        board[x][y] -= 1; board[nx][ny] += 1;
        if(board[x][y] == 0) offset += 1;
        ans = max(ans, offset + solve(nxt.first, nxt.second));
        board[nx][ny] -= 1; board[x][y] += 1;
    }
   
    if(y == 0 && x > 0){
        vis[x][pstate][cstate] = true;
        dp[x][pstate][cstate] = ans;
    }
    return ans;
}
int main(){
    cin>>N>>M;
    if(M > N) swap(N, M);
    for(int i=0;i<N;i++) for(int j=0;j<M;j++) board[i][j] = 1;
    cout<<solve(0, 0)<<endl;
    return 0;
}